package 剑指II;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-28
 **/

public class Jz087复原IP {

    /**
     * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
     * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
     * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，
     * 但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
     * <p>
     * 示例 1：
     * 输入：s = "25525511135"
     * 输出：["255.255.11.135","255.255.111.35"]
     * 示例 2：
     * 输入：s = "0000"
     * 输出：["0.0.0.0"]
     * 示例 3：
     * 输入：s = "1111"
     * 输出：["1.1.1.1"]
     * 示例 4：
     * 输入：s = "010010"
     * 输出：["0.10.0.10","0.100.1.0"]
     * 示例 5：
     * 输入：s = "10203040"
     * 输出：["10.20.30.40","102.0.30.40","10.203.0.40"]
     * <p>
     * 提示：
     * 0 <= s.length <= 3000
     * s 仅由数字组成
     * <p>
     * 注意：本题与主站 93 题相同：https://leetcode-cn.com/problems/restore-ip-addresses/ 
     */

    public List<String> restoreIpAddresses(String s) {

        List<String> result = new ArrayList<>();

        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                for (int k = 1; k <= 4; k++) {
                    for (int l = 1; l <= 4; l++) {
                        if (i + j + k + l == s.length()) {
                            int index1 = i;
                            int index2 = i + j;
                            int index3 = i + j + k;
                            int index4 = i + j + k + l;
                            int a = Integer.parseInt(s.substring(0, index1));
                            int b = Integer.parseInt(s.substring(index1, index2));
                            int c = Integer.parseInt(s.substring(index2, index3));
                            int d = Integer.parseInt(s.substring(index3, index4));
                            if (a <= 255 && b <= 255 && c <= 255 && d <= 255) {
                                String resultItem = "" + a + "." + b + "." + c + "." + d;
                                if (resultItem.length() == s.length() + 3) {
                                    // 预防前导0的情况
                                    result.add(resultItem);
                                }
                            }

                        }
                    }
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Jz087复原IP n = new Jz087复原IP();
        List<String> result = n.restoreIpAddresses("01000");
        System.out.println(JSON.toJSONString(result));
    }

}
